几种常见的排序

2018-05-03

iOS开发

code

1.冒泡排序

/* 冒泡排序 */
    for (int end = cnt - 1; end > 0 ; end --) {
        for (int begin = 1; begin <= end; begin ++) {
            // 优化-减少已排序部分的比较
            int startIndex = 1;
            if (array[begin - 1] < array[begin]) {
                int tmp = array[begin - 1];
                array[begin - 1] = array[begin];
                array[begin] = tmp;
                startIndex = begin;
            }
            end = startIndex;
        }
    }

2.选择排序

// - 比较后，记录最大索引，最后进行交换。
for (int end= cnt - 1; end > 0; end--) {
        int maxIndex = 0;
        for (int begin = 1; begin <= end; begin++) {
            if(array[maxIndex] <= array[begin]) {
                maxIndex = begin;
            }
        }
        int tmp = array[end];
        array[end] = array[maxIndex];
        array[maxIndex] = tmp;
 }

3.堆排序

int array[] = {9, 5, 2, 7};
int heapSize = array.length;

void sort() {
  heapify();
  while (heapSize > 1) {
    int tmp = array[heapSize - 1];
     array[heapSize - 1] = array[0];
    array[0] = temp;
    heapSize--;
   siftDown(0);
  }
}

// 建堆
void heapify() {
  for (int i = (heapSize >> 1) - 1; i >= 0; i --) {
      siftDown(i);
  }
}
// 自下而上的下滤
void siftDown(int index) {
      int current = array[index];
      int half = heapSize >> 1;
      while (index < half) {
        int childIndex = (index << 1) + 1;
        int child = array[childIndex];
        int rightIndex = childIndex + 1;
        if (rightIndex < heapSize && array[rightIndex] > child) {
            child = array[childeIndex = rightIndex];
        }
        if (current >= child) break;
        array[index] = child;
        index = childIndex;
      }
      array[index] = current;
}

4.插空排序

代码解析见注释。

int  a[5]={9, 8, 10, 2, 20};
// key为每次被拿出的值（也就是初始提供“空”的值），j为要比较到的最大索引
int key,j;
// 直接插入排序
for (int i=1; i<5; i++) {
    // 取出当前要比较项
    key=a[i];
    // 和直到索引j位置的元素逐一比较
    for (j=i-1; j>=0&&a[j]>key; j--) {
        // j为更新出来的新空
        a[j+1]=a[j];
    }
    // 因为循环结束时进行一次j--操作，所以下面要+1
    // j+1为最后留给key的空
    a[j+1]=key;
}
// 另一种写法
for (int begin=1; begin < 5; begin++) {
    // 记录当前索引（当前空位）
    int cur = begin;
    int val = a[cur];
    // 和直到索引j位置的元素逐一比较
    while (cur > 0 && val > a[cur - 1]) {
        // j为更新出来的新空
        a[cur] = a[cur - 1];
        cur --;
    }
    a[cur] = val;
}

二分查找

// 返回找到的元素对应的索引，没找到返回-1
int binarySearch(int array[], int v) {
  if (array == null || array.length == 0) {
      retrun -1;
  }
  int begin = 0;
  int end = array.length;
  while (begin < end) {
       int mid = (begin + end) >> 1;
       if (v > array[mid]) {
          begin = mid + 1;
       } else if (v < array[mid]) {
          end = mid;
      } else {
          return mid;
      }
  }
  return -1;
}

结合二分查找优化插空排序

void insertSort(int [] array) {
  for (int begin = 1; begin < array.length; begin++) {
      insert(begin, search(begin));
  }
}
// 执行插入的元素位移操作
void insert(int source, int target) {
      int v = array[source];
      for (int i = source; i > target; i --) {
            array[source] = array[source - 1];
      }
      array[target] = v;
}
// 用二分法查找当前取出的元素在已排好序部分对应的插入位置
int search(int index) {
    int v = array[index];
    int begin = 0;
    int end = index;
    while (begin < end) {
       int mid = (begin + end) >> 1;
       if (v >= array[mid]) {
          begin = mid + 1;
       } else {
          end = mid;
       }
    }
   return begin;
}

5.归并排序

int[] array = {9, 5, 2, 7};
void mergeSort() {
      sortRecursive(0, array.length);
}

void sortRecursive(int begin, int end) {
      // 数组只剩一个元素，不能再分了
      if (end - begin < 2) return;
      int mid = (begin + end) >> 1;
      sortRecursive(begin, mid);
      sortRecursive(mid, end);
      merge(begin, mid, end);
}
// 用来存放左边排好序部分的备用数组
int leftArray[] = new int[array.length >> 1];
void merge(int begin, int mid, int end) {
      int lp = 0, le = mid - begin;
      int rp = mid, re = end;
      int ap = begin;
      for (int i = 0; i < le; i ++) {
          leftArray[i] = array[begin + i];
      }
      // 只要左边结束了，整个排序就结束了
      while (lp < le) {
            if (rp < re &&  array[rp] < leftArray[lp]) {
                array[ap++] = array[rp++];
            } else {
                array[ap] = leftArray[lp];
                ap ++;
                lp ++;
           }
      }
}

6.快速排序

int[] array = {9, 5, 2, 7};
void pivotSort() {
      pivotRecursive(0, array.length);
}

void pivotRecursive(int begin, int end) {
      if (end - begin < 2) return;
      // 找到轴点的位置
      int pivot = pivotIndex(begin, end);
      // 递归轴点左
      pivotRecursive(begin, pivot);
      // 递归轴点右
      pivotRecursive(pivot + 1, end);
}

int pivotIndex(int begin, int end) {
   // 优化：为了轴点左右数据更加均衡，随机选择轴点
   int random = random(end - begin);
   int tmp = array[begin];
   array[begin] = array[random];
   array[random] = tmp;
   
   int v = array[begin];
   // 因为end是从array.length开始的，所以要--
   end--;
   // 嵌套while循环实现左右交替执行
   while (begin < end) {
           while (begin < end) {
                   if (array[end] > v) {
                      end--;
                  } else {
                      array[begin++] = array[end]; 
                      break;
                  }
           }
           while (begin < end) {
                   if (array[begin] < v) {
                      begin++;
                  } else {
                      array[end--] = array[begin]; 
                      break;
                  }
           }
   }
   array[begin] = v;
   return begin
}

7.希尔排序

可看作是对插空排序的优化

int[] array = {9, 5, 2, 7};
void shellSort() {
      int[] steps = step(array.length);
      for (int i = 0; i < steps.length; i ++) {
           int step = steps[i];
           for (int col = 0; col < step; col ++) {
              for (int begin = col + step; begin < array.length; begin += step) {
              int cur = begin;
              int v = array[cur];
              while (cur > col && v > array[cur - step]) {
                      array[cur] = array[cur - step];
                      cur -=step;
              }
              arrau[cur] = v; 
           }
          } 
      }
}
// 创建步长数组
int[] step(int step) {
    int[] steps = new int[];
    while ((step >>= 1) > 0) {
          steps.add(step)
    }
    return step;
}

8.计数排序

中心思想：用空间换时间

只适用于一定范围内的整数排序

int[] array = {9, 5, 2, 7};
// 仅支持正整数版本
// 找出最大值
int max = array[0];
for (int i = 1; i < array.length; i ++) {
    if (array[i] > max) {
      max = array[i];
    }
}
// 创建计数数组
int[] counts = new int[max + 1];
for (int i = 0; i < array.length; i ++) {
    conuts[array[i]] += 1;
}
// 输出排好序的数组
int index = 0;
for (int i = 0; i < counts.length; i ++) {
    while ((counts[i]--) > 0) {
         array[index++] = i;
    }
}

// 优化版本，支持负整数(包含整数属性排序的自定义对象也可以)
// 找出最大值，最小值
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i ++) {
    if (array[i] > max) {
      max = array[i];
    }
    if (array[i] < min) {
      min = array[i];
    }
}
// 计数数组
int[] counts = new int[max - min + 1];
for (int i = 0; i < array.length; i ++) {
    conuts[array[i] - min] += 1;
}
// 累加次数
for （int i = 1; i < counts.length; i++) {
    counts[i] += counts[i - 1];
}
// 从后往前遍历元素，将它放到有序数组中的合适位置
int newArray = new int[array.length];
for (int i = array.length - 1; i >=0; i --) {
    newArray[--counts[array[i] - min]] = array[i];
}
// 将有序数组赋值到array
for (int i = 0; i < array.length; i ++) {
    array[i] = newArray[i];
}

9.基数排序

数据从低位到高位按位排序

排序用计数排序

int[] array = {9, 5, 2, 7};
// 仅支持正整数版本
// 找出最大值
int max = array[0];
for (int i = 1; i < array.length; i ++) {
    if (array[i] > max) {
      max = array[i];
    }
}
// 创建计数数组
int[] counts = new int[max + 1];
for (int devider = 1; devider < max; devider * 10) {
    countingSort(devider);
}

void countingSort(int devide) {
     // 计数数组
    int[] counts = new int[10];
    for (int i = 0; i < array.length; i ++) {
       conuts[array[i] / devide % 10] += 1;
    }
    // 累加次数
    for （int i = 1; i < counts.length; i++) {
       counts[i] += counts[i - 1];
   }
   // 从后往前遍历元素，将它放到有序数组中的合适位置
   int newArray = new int[array.length];
   for (int i = array.length - 1; i >=0; i --) {
      newArray[--counts[array[i] / devide % 10]] = array[i];
   }
   // 将有序数组赋值到array
   for (int i = 0; i < array.length; i ++) {
       array[i] = newArray[i];
   }
}

10.桶排序

自定义规则
按规则尽量均匀分布数据到每个桶
对桶内数据排序
将桶内数据串起来

以上均为伪代码，仅提供思路

整体测试代码


#import <Foundation/Foundation.h>
void initArray(int array[],int cnt);
void selectSortForArray(int array[],int cnt);
void showArray(int array[],int cnt);


void initArray(int array[],int cnt)
{
    for(int i= 0;i<cnt;i++)
        array[i] = arc4random()  % 100;
}
void selectSortForArray(int array[],int cnt)
{
    /*for (int i = 0; i<cnt-1; i++){
        for (int j = i+1; j<cnt; j++)
        {if (array[i] < array[j]) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
     }}}*/
    //****************这样每次比较后都交换元素位置**********
    for (int i= 0;i<cnt-1;i++){
        for (int j=i + 1;j<cnt;j++){
            if(array[i]<array[j]){
                int tmp=array[i];
                array[i]=array[j];
                array[j]=tmp;
            }
        }
//    }
//*****************这样每次比较只记住索引，内循环遍历一次完成后再交换（减少交换次数），*********
    for (int i = 0; i < cnt - 1; i++) {
        int tmp = 0;
        for (int j = i + 1; j < cnt; j++) {
            if (array[i] < array[j]) {
                tmp = j;
            }
            int c = array[i];
            array[i] = array[tmp];
            array[tmp] = c;
        }
    }
    /* 冒泡排序 */
    for (int i = 0; i < cnt - 1; i ++) {
        for (int j = 0; j < cnt - i - 1; j ++) {
            if (array[j] < array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}
void showArray(int array[],int cnt)
{
    for (int i = 0; i<cnt; i++) {
        printf("%d ",array[i]);
    }
    printf("\n");
}

int main(int argc, const char * argv[])
{

    @autoreleasepool {
        
        // insert code here...
//        NSLog(@"Hello, World!");
//
        int array[10] = {0};
        initArray(array, 10);
        showArray(array,10);
        selectSortForArray(array, 10);
        showArray(array,10);
        
        // C-实现 插空排序
        int  a[5]={9,8,10,2,20};
        int key,j;// key为每次被拿出的值（也就是初始提供“空”的值），j为要比较到的最大索引
        for (int i=1; i<5; i++) {// 直接插入排序
            key=a[i];// 取出当前要比较项
            for (j=i-1; j>=0&&a[j]>key; j--) {// 和直到索引j位置的元素逐一比较
                a[j+1]=a[j];// j为更新出来的新空（但是只要进了循环，此次循环结束就会进行一次j--操作，所以下面要+1）
            }
            a[j+1]=key;// j+1为最后留给key的空
        }
        for (int i=0; i<5; i++) {
//            NSLog(@"%i",a[i]);
        }
        // OC实现
//        NSMutableArray *array=[NSMutableArray arrayWithObjects:@9,@8,@10,@2,@20, nil];
//        id key;
//        NSInteger j;
//        for (NSInteger i=1; i<array.count; i++) {
//            key=[array objectAtIndex:i];//取到每一个待插入的数据,从a[1]开始查找
//            for (j=i-1; j>=0&&array[j]>key; j--) {
//                // 如果之前的数比key大,就将这个数向后移动一个位置,留出空来让key插入就像整牌一样
//
//                [array exchangeObjectAtIndex:j+1 withObjectAtIndex:j];//交换
//            }
//            [array replaceObjectAtIndex:j+1 withObject:key];
//        }
//        for (key in array) {
//            NSLog(@"%@",key);
//        }
        printf("\n");
    }
    return 0;
}